package xyz.naokeziteng.sort;

import java.util.Arrays;

/**
 * @author hawk
 * @date 2022/8/15
 * @desc 归并排序
 **/
public class MergeSort {


    public static void mergeSort(int[] arr, int s, int e) {
        if (s >= e) {
            return;
        }
        int m = (s + e) / 2;
        mergeSort(arr, s, m);
        mergeSort(arr, m + 1, e);

        //合并
        merge(arr, s, m, e);
    }

    /**
     * 合并
     *  arr[l,mid] arr[mid+1,r]
     * @param arr 数组
     * @param l   起点
     * @param mid 中间点
     * @param r   终点
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        int[] aux = Arrays.copyOfRange(arr, l, r + 1);

        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {

            if (i > mid) {  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l] < aux[j - l]) {  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i - l];
                i++;
            } else {  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 6, 2, 4, 7, 8};
        //merge(arr, 0, 3, 7);
        mergeSort(arr, 0, 7);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
